package xyz.naokeziteng.serach;

/**
 * 二分查找 O(log(n))
 */
public class BinarySearch {

    public static int search(int[] arr, int n) {
        return binarySearch2(arr, 0, arr.length - 1, n);
    }



    public static int binarySearch(int[] arr, int l, int r, int n) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (arr[mid] > n) {
            return binarySearch(arr, l, mid - 1, n);
        } else if (arr[mid] < n) {
            return binarySearch(arr, mid + 1, r, n);
        } else {
            return mid;
        }
    }

    //n in arr[l,r]
    public static int binarySearch2(int[] arr, int l, int r, int n) {
        int i = l;
        int j = r;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (arr[mid] > n) {
                j = mid - 1;
            } else if (arr[mid] < n) {
                i = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(search(arr, 8));
        System.out.println(search(arr, 1));
        System.out.println(search(arr, 3));
        System.out.println(search(arr, 9));
    }
}
